{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Handshakes That Don't Cross"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不相交的握手"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>偶数</strong>&nbsp;个人站成一个圆，总人数为&nbsp;<code>num_people</code>&nbsp;。每个人与除自己外的一个人握手，所以总共会有&nbsp;<code>num_people / 2</code>&nbsp;次握手。</p>\n",
    "\n",
    "<p>将握手的人之间连线，请你返回连线不会相交的握手方案数。</p>\n",
    "\n",
    "<p>由于结果可能会很大，请你返回答案 <strong>模</strong>&nbsp;<strong><code>10^9+7</code></strong>&nbsp;后的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num_people = 2\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/11/16/5125_example_2.png\" style=\"height: 311px; width: 651px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num_people = 4\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>总共有两种方案，第一种方案是 [(1,2),(3,4)] ，第二种方案是 [(2,3),(4,1)] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/11/16/5125_example_3.png\" style=\"height: 992px; width: 664px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num_people = 6\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num_people = 8\n",
    "<strong>输出：</strong>14\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= num_people &lt;= 1000</code></li>\n",
    "\t<li><code>num_people % 2 == 0</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [handshakes-that-dont-cross](https://leetcode.cn/problems/handshakes-that-dont-cross/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [handshakes-that-dont-cross](https://leetcode.cn/problems/handshakes-that-dont-cross/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4', '6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "state = [1] * 501\n",
    "for i in range(1, 501):\n",
    "    state[i] = sum(state[j]*state[i-1-j] for j in range(i)) % MOD\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        # 只与人数n=numPeople/2有关，人数总为偶数，state[n]存储的是握手方案数\n",
    "        # state[n] = state[n-1]*  状态转移方程怎么写\n",
    "        return state[numPeople // 2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int) -> int:\n",
    "        # Catalan\n",
    "        return (math.factorial(n) // math.factorial(n//2) // math.factorial(n//2+1)) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        # 1 可以和 2， 4， 6， 8....连接\n",
    "        # 左边有0， 2， 4， 6个\n",
    "        # 右边有n-2, n-2-2, n-2-4, n-2-6\n",
    "        # dp[i] 代表 i*2有多少个连接\n",
    "        dp = [0] * ((numPeople >> 1) + 1)\n",
    "        dp[0], dp[1] = 1, 1\n",
    "        for i in range(2, (numPeople >> 1) + 1):\n",
    "            for j in range(i):\n",
    "                dp[i] += dp[j] * dp[i-j-1]\n",
    "                dp[i] %= (10**9+7)\n",
    "        \n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        # 1 可以和 2， 4， 6， 8....连接\n",
    "        # 左边有0， 2， 4， 6个\n",
    "        # 右边有n-2, n-2-2, n-2-4, n-2-6\n",
    "        # dp[i] 代表 i*2有多少个连接\n",
    "        dp = [0] * ((numPeople >> 1) + 1)\n",
    "        dp[0], dp[1] = 1, 1\n",
    "        for i in range(2, (numPeople >> 1) + 1):\n",
    "            for j in range(i):\n",
    "                dp[i] += dp[j] * dp[i-j-1]\n",
    "            dp[i] %= (10**9+7)\n",
    "        \n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        dp = [0]*(numPeople+1)\n",
    "        dp[2] = 1\n",
    "        dp[0]= 1\n",
    "        for i in range(4, numPeople+1, 2):\n",
    "            for j in range(0, i+1, 2):\n",
    "                dp[i] += dp[j]*dp[i-j-2]%mod\n",
    "        return dp[numPeople]%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        p = 1000000007\n",
    "        lst = [0] * (numPeople + 1)\n",
    "        lst[0] = 1\n",
    "        for i in range(2, numPeople + 1, 2):\n",
    "            for j in range(0, i, 2):\n",
    "                lst[i] += (lst[j] * lst[i - 2 - j]) % p\n",
    "                lst[i] %= p\n",
    "        return lst[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        n = numPeople\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        for i in range(2, n+1, 2):\n",
    "            for j in range(2, i+1, 2):\n",
    "                dp[i] += (dp[j - 2] * dp[i - j]) % (10 ** 9 + 7)\n",
    "        return dp[n] % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        n = numPeople//2\n",
    "        dp = [0]*(n+1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(0,i):\n",
    "                left,right = j,i-j-1\n",
    "                dp[i] = (dp[i] + dp[left] * dp[right])%MOD\n",
    "            pass\n",
    "        return dp[-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = numPeople\n",
    "        dp = [1, 1] + [0] * (n - 1)\n",
    "        for i in range(2, n+1, 2):\n",
    "            for j in range(1, i, 2):\n",
    "                dp[i] += dp[j - 1] * dp[i-j-1]\n",
    "                dp[i] %= mod\n",
    "\n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        # 1 可以和 2， 4， 6， 8....连接\n",
    "        # 左边有0， 2， 4， 6个\n",
    "        # 右边有n-2, n-2-2, n-2-4, n-2-6\n",
    "        # dp[i] 代表 i*2有多少个连接\n",
    "        dp = [0] * ((numPeople >> 1) + 1)\n",
    "        dp[0], dp[1] = 1, 1\n",
    "        for i in range(2, (numPeople >> 1) + 1):\n",
    "            for j in range(i):\n",
    "                dp[i] += dp[j] * dp[i-j-1]\n",
    "            dp[i] %= (10**9+7)\n",
    "        \n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        n = numPeople//2\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i):\n",
    "                dp[i]+= dp[i-1-j]*dp[j]\n",
    "\n",
    "        return int(dp[n]%(10**9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        n=numPeople\n",
    "        MOD = 10**9 + 7\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n==2:\n",
    "            return 1\n",
    "        res=[0 for _ in range(n+1)]\n",
    "        res[0]=1\n",
    "        res[2]=1\n",
    "        res[4]=2\n",
    "        for i in range(6,n+1,2):\n",
    "            for j in range(1,i,2):\n",
    "                res[i]=(res[i]+(res[j-1]*res[i-j-1])%MOD)%MOD\n",
    "        return res[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        dp=[0]*(numPeople+1)\n",
    "        dp[0]=1\n",
    "        dp[2]=1\n",
    "        for i in range(2,numPeople//2+1):\n",
    "            for j in range(i):\n",
    "                dp[2*i]+=dp[j*2]*dp[i*2-2*j-2]\n",
    "        return dp[numPeople]%(1000000000+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        \"\"\"\n",
    "        dp[n] = sum(dp[2 * j - 2] * dp[n - 2 * j])\n",
    "        \"\"\"\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        dp = [1] * (numPeople + 1)\n",
    "        for i in range(1, numPeople + 1):\n",
    "            dp[i] = sum(dp[j] * dp[i - j - 1] for j in range(i)) % mod\n",
    "        return dp[numPeople // 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, num_people: int) -> int:\n",
    "        mod = 1000000007\n",
    "        n = num_people\n",
    "        dp = [1] * (n+1)\n",
    "        for i in range(2, n+1, 2):\n",
    "            dp[i] = 0\n",
    "            for j in range(1, i, 2):\n",
    "                dp[i] = (dp[i] + (dp[j-1]*dp[i-j-1])%mod)%mod\n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "dp = [1] * 501\n",
    "for i in range(1, 501):\n",
    "    dp[i] = sum(dp[j] * dp[i - 1 - j] for j in range(i)) % MOD\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        return dp[numPeople // 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [0] * (numPeople // 2 + 1) # 要 n 对 + 1的长度存储结果\n",
    "        dp[0] = 1  # 基础情况，没有人时有1种配对方式\n",
    "        \n",
    "        # 之所以除以2, 是以为前半部分和后半部分的答案是对称的, 所以只要前半部分 + 中间部分就好了\n",
    "        for i in range(1, numPeople // 2 + 1):\n",
    "            for j in range(i):\n",
    "                dp[i] = (dp[i] + dp[j] * dp[i - j - 1]) % mod \n",
    "        \n",
    "        return dp[numPeople // 2]  # 返回配对方式数量\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        num = numPeople // 2\n",
    "        dp = [1] * (num + 1)\n",
    "        for i in range(2, num + 1):\n",
    "            dp[i] = sum(dp[j] * dp[i - j - 1] for j in range(i)) % mod\n",
    "        return dp[num]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int) -> int:\n",
    "        MOD=10**9+7\n",
    "        dp=[0]*(n+1)\n",
    "        #dp[i]表示i个人合法的握手方案数,可以递推看状态转移\n",
    "        dp[0]=1\n",
    "        dp[2]=1\n",
    "        for i in range(4,n+1,2):\n",
    "            for j in range(0,n-1,2):\n",
    "                dp[i]=(dp[i]+dp[j]*dp[i-2-j])%MOD\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = numPeople\n",
    "        f = [0] * (n + 1)\n",
    "        f[0] = 1\n",
    "        f[2] = 1\n",
    "        for i in range(4, n + 1, 2):\n",
    "            for j in range(2, i + 1):\n",
    "                if (j - 1 - 1) % 2:\n",
    "                    continue\n",
    "                else:\n",
    "                    f[i] = (f[i] + (f[j - 1 - 1] * f[i - j]) % mod ) % mod\n",
    "        return f[n]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        # 只与人数n=numPeople/2有关，人数总为偶数，state[n]存储的是握手方案数\n",
    "        # state[n] = state[n-1]*  状态转移方程怎么写\n",
    "        MOD = 10**9 + 7\n",
    "        state = [1] * 501\n",
    "        for i in range(1, 501):\n",
    "            state[i] = sum(state[j]*state[i-1-j] for j in range(i)) % MOD\n",
    "        return state[numPeople // 2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        n = numPeople // 2 + 1\n",
    "        dp = [1] * n\n",
    "        for i in range(1, n):\n",
    "            dp[i] = sum(dp[j] * dp[i - 1 - j] for j in range(i)) % MOD\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        # 1 可以和 2， 4， 6， 8....连接\n",
    "        # 左边有0， 2， 4， 6个\n",
    "        # 右边有n-2, n-2-2, n-2-4, n-2-6\n",
    "        # dp[i] 代表 i*2有多少个连接\n",
    "        dp = [0] * ((numPeople >> 1) + 1)\n",
    "        dp[0], dp[1] = 1, 1\n",
    "        for i in range(2, (numPeople >> 1) + 1):\n",
    "            for j in range(i):\n",
    "                dp[i] += dp[j] * dp[i-j-1]\n",
    "            dp[i] %= (10**9+7)\n",
    "        \n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        # 1 可以和 2， 4， 6， 8....连接\n",
    "        # 左边有0， 2， 4， 6个\n",
    "        # 右边有n-2, n-2-2, n-2-4, n-2-6\n",
    "        # dp[i] 代表 i*2有多少个连接\n",
    "        dp = [0] * ((numPeople >> 1) + 1)\n",
    "        dp[0], dp[1] = 1, 1\n",
    "        for i in range(2, (numPeople >> 1) + 1):\n",
    "            for j in range(i):\n",
    "                dp[i] += dp[j] * dp[i-j-1]\n",
    "            dp[i] %= (10**9+7)\n",
    "        \n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        dp = [0] * (numPeople+1)\n",
    "        dp[0] = 1\n",
    "        dp[2] = 1\n",
    "        for n in range(4, numPeople + 1, 2):\n",
    "            for m in range(0, n//2):\n",
    "                j = 2*m + 1\n",
    "                dp[n] += dp[j - 1]*dp[n-j-1]\n",
    "\n",
    "        return int(dp[numPeople] % mod)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        # 1 可以和 2， 4， 6， 8....连接\n",
    "        # 左边有0， 2， 4， 6个\n",
    "        # 右边有n-2, n-2-2, n-2-4, n-2-6\n",
    "        # dp[i] 代表 i*2有多少个连接\n",
    "        dp = [0] * ((numPeople >> 1) + 1)\n",
    "        dp[0], dp[1] = 1, 1\n",
    "        for i in range(2, (numPeople >> 1) + 1):\n",
    "            for j in range(i):\n",
    "                dp[i] += dp[j] * dp[i-j-1]\n",
    "            dp[i] %= (10**9+7)\n",
    "        \n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "dp = [1] * 501\n",
    "for i in range(1, 501):\n",
    "    dp[i] = sum(dp[j] * dp[i - 1 - j] for j in range(i)) % mod\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        return dp[numPeople // 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        \n",
    "        # top to bottom\n",
    "        # cache={}\n",
    "\n",
    "        # def dp_helper(n):\n",
    "        #     if  n==0:\n",
    "        #         return 1\n",
    "        #     if n in cache:\n",
    "        #         return cache[n]\n",
    "        #     total=0\n",
    "        #     for i in range(n//2):\n",
    "        #         total +=dp_helper(i*2)*dp_helper(n-(i+1)*2)\n",
    "        #     cache[n] =total\n",
    "        #     return cache[n]\n",
    "        # return dp_helper(numPeople) %(10**9 + 7)\n",
    "\n",
    "        # bottom to top\n",
    "        \n",
    "        cache =[0]* (numPeople//2+1)\n",
    "        cache[0]=1\n",
    "        for i in range(1,numPeople//2+1):\n",
    "            total =0\n",
    "            for j in range(i):\n",
    "                total+=cache[j]* cache[i-j-1]\n",
    "            cache[i]=total\n",
    "\n",
    "        return cache[-1]%(10**9+7)\n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        num = numPeople // 2\n",
    "        dp = [1] * (num +1)\n",
    "        for i in range(2, num + 1):\n",
    "            dp[i] = sum(dp[j] * dp[i - j - 1] for j in range(i)) % mod\n",
    "        return dp[num]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = numPeople\n",
    "        f = [1] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            f[i] = 0\n",
    "            for j in range(1, i, 2):\n",
    "                f[i] = (f[i] + (f[j - 1] * f[i - j - 1]) % mod) % mod\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        mod = 1000000007\n",
    "        dp= [1 for i in range(numPeople+1)]\n",
    "        for i in range(2, numPeople+1, 2):\n",
    "            dp[i]=0\n",
    "            for j in range(1, i, 2):\n",
    "                dp[i] = (dp[i] + (dp[j-1]*dp[i-j-1])%mod)%mod\n",
    "        return dp[numPeople]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        dp=[0]*(numPeople//2+1)\n",
    "        dp[1]=1\n",
    "        dp[0]=1\n",
    "        for i in range(2,numPeople//2+1):\n",
    "            t=0\n",
    "            for j in range(i):\n",
    "                t+=dp[j]*dp[i-j-1]\n",
    "            dp[i]=t\n",
    "        return dp[-1] %(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = numPeople\n",
    "        f = [1] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            f[i] = 0\n",
    "            for j in range(1, i, 2):\n",
    "                f[i] = (f[i] + (f[j - 1] * f[i - j - 1]) % mod) % mod\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        if numPeople==2:\n",
    "            return 1\n",
    "        if numPeople==4:\n",
    "            return 2\n",
    "        dq=[0 for i in range(numPeople//2+1)]\n",
    "        dq[0]=1\n",
    "        dq[1]=1\n",
    "        dq[2]=2\n",
    "        for i in range(3,numPeople//2+1):\n",
    "            for j in range(i):\n",
    "                dq[i]+=dq[i-j-1]*dq[j]\n",
    "                dq[i]=dq[i]%(10**9+7)\n",
    "        return dq[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        MOD = int(1e9+7)\n",
    "        n = numPeople\n",
    "        f = [0]*(n + 1)\n",
    "        f[0] = 1\n",
    "        f[1] = 1\n",
    "        for i in range(2,n + 1,2):\n",
    "            for j in range(1,i,2):\n",
    "                f[i] += f[j - 1]*f[i - 1 - j] % MOD\n",
    "                f[i] %= MOD\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int) -> int:\n",
    "        MOD=10**9+7\n",
    "        dp=[0]*(n+1)\n",
    "        #dp[i]表示i个人合法的握手方案数,可以举例子递推看状态转移\n",
    "        dp[0]=1\n",
    "        dp[2]=1\n",
    "        for i in range(4,n+1,2):\n",
    "            for j in range(0,n-1,2):\n",
    "                dp[i]=(dp[i]+dp[j]*dp[i-2-j])%MOD\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        \n",
    "\n",
    "        n=numPeople//2\n",
    "        if n==0: return 0\n",
    "        if n==1: return 1\n",
    "        if n==2: return 2\n",
    "        dp = [0] * (n+1)\n",
    "        dp[0]=1\n",
    "        dp[1]=1\n",
    "        dp[2]=2\n",
    "        for i in range(3,n+1):\n",
    "            t=0\n",
    "            for j in range(i):\n",
    "                t+=dp[j]*dp[i-j-1]\n",
    "            dp[i]=t\n",
    "        print(dp)\n",
    "        return dp[-1]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        n = numPeople\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        for i in range(2, n+1, 2):\n",
    "            for j in range(1, i+1, 2):\n",
    "                dp[i] += (dp[j-1] * dp[i - j - 1]) % (10 ** 9 + 7)\n",
    "        return dp[n] % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        dp = [0 for _ in range(numPeople+1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(2, numPeople+1, 2):\n",
    "            for j in range(i//2+1):\n",
    "                dp[i] = (dp[i] + dp[j*2-2] * dp[i-2*j] % 1000000007) % 1000000007\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        # 如果只有两个人，那么只有一次握手\n",
    "        # 如果有四个人，那么有两次握手\n",
    "        # 如果有六个人，那么可以分成两个人和四个人，两个人有一次握手，四个人有两次，1 * 2 = 2，\n",
    "        n = numPeople\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(2, n + 1, 2):\n",
    "            for j in range(0, i - 1, 2):\n",
    "                dp[i] += dp[j] * dp[i - j - 2]\n",
    "        return dp[-1] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        MOD = 10**9 + 7  # 为了防止整数溢出，通常需要模一个大素数\n",
    "        # 初始化dp数组，所有值设为0\n",
    "        dp = [0] * (numPeople // 2 + 1)\n",
    "        dp[0] = 1  # 基础情况，没有人时有1种配对方式\n",
    "        \n",
    "        # 填充dp数组\n",
    "        for i in range(1, numPeople // 2 + 1):\n",
    "            for j in range(i):\n",
    "                dp[i] = (dp[i] + dp[j] * dp[i - j - 1]) % MOD\n",
    "        \n",
    "        return dp[numPeople // 2]  # 返回配对方式数量\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        \"\"\"\n",
    "        固定第n个人，可以和1～n-1握手\n",
    "        左边i-1个人，右边n-1-i个人\n",
    "        f(n) = sum(i in range(1, n, 2)) [f(i-1)+f(n-1-i)]\n",
    "        \"\"\"\n",
    "        temp = [0]*int(numPeople+1)\n",
    "        temp[0] = 1\n",
    "        temp[2] = 1\n",
    "        n = numPeople\n",
    "        for i in range(4, n+1, 2):\n",
    "            temp[i] = sum([temp[j-1]*temp[i-1-j] for j in range(1, i, 2)])\n",
    "        # print(temp[n])\n",
    "        return int(temp[n]%(pow(10,9)+7))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        dp=[0]*(numPeople//2+1)\n",
    "        dp[1]=1\n",
    "        dp[0]=1\n",
    "        for i in range(2,numPeople//2+1):\n",
    "            t=0\n",
    "            for j in range(i):\n",
    "                t+=dp[j]*dp[i-j-1]\n",
    "            dp[i]=t\n",
    "        print(dp)\n",
    "        return dp[-1] if dp[-1]<10**9+7 else dp[-1] %(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        @cache\n",
    "        def dfs(n):\n",
    "            if n%2==1:\n",
    "                return 0\n",
    "            if n<=2:\n",
    "                return 1\n",
    "            ans=0\n",
    "            for i in range(0,n-1,2):\n",
    "                ans+=dfs(i)*dfs(n-2-i)   \n",
    "            return ans%(10**9+7) \n",
    "        return dfs(numPeople)  \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def get_ans(n):\n",
    "            if n <= 1: return 1\n",
    "            return sum([get_ans(i) * get_ans(n - i - 1) for i in range(n)]) % (10 ** 9 + 7)\n",
    "        return get_ans(numPeople // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "        @cache\n",
    "        def dfs(num):\n",
    "            if num==0:\n",
    "                return 1\n",
    "            elif num==2:\n",
    "                return 1\n",
    "            ret=0\n",
    "            for i in range(1,num//2,2):\n",
    "                ret += dfs(i-1)*dfs(num-i-1)\n",
    "            ret*=2\n",
    "            if num//2%2==1:\n",
    "                ret += dfs(num//2-1)**2\n",
    "            return ret\n",
    "        return dfs(numPeople)%(1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, numPeople: int) -> int:\n",
    "\n",
    "        cache={}\n",
    "\n",
    "        def dp_helper(n):\n",
    "            if n==2 or n==0:\n",
    "                return 1\n",
    "            if n in cache:\n",
    "                return cache[n]\n",
    "            total=0\n",
    "            for i in range(n//2):\n",
    "                total +=dp_helper(i*2)*dp_helper(n-(i+1)*2)\n",
    "            cache[n] =total\n",
    "            return cache[n]\n",
    "        return dp_helper(numPeople) %(10**9 + 7)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
